#ifndef _LIST_GRAPH_H_
#define _LIST_GRAPH_H_

#include "Object.h"
#include "Graph.h"
#include "Exception.h"
#include "DualLinkList.h"
#include "DynamicArray.h"

namespace MySTL
{

template < typename V, typename E >
class ListGraph : public Graph<V, E>
{
public:
	ListGraph(int n = 0);
	~ListGraph();

	int addVertex();
	int addVertex(const V& value);
	void removeVertex();
	V& getVertex(int n);
	const V& getVertex(int n) const;
	bool getVertex(int n, V& value) const;
	bool setVertex(int n, const V& value);
	SharedPointer< Array<int> > getAdjacent(int n) const;
	E& getEdge(int i, int j);
	const E& getEdge(int i, int j) const;
	bool getEdge(int i, int j, E& value) const;
	bool setEdge(int i, int j, const E& value);
	bool removeEdge(int i, int j);
	int VCount() const;
	int ECount() const;
	int IDegree(int n) const;
	int ODegree(int n) const;
	bool isAdjacent(int i, int j) const;

protected:
	struct Vertex : public Object
	{
		V* data;
		DualLinkList< Edge<E> > edgeList;

		Vertex();
	};

protected:
	mutable DualLinkList<Vertex*> m_vertexList;
};

template < typename V, typename E >
ListGraph<V, E>::Vertex::Vertex()
{
	data = NULL;
}

template < typename V, typename E >
ListGraph<V, E>::ListGraph(int n)
{
	if (n > 0)
	{
		for (int i = 0; i < n; ++i)
		{
			addVertex();
		}
	}
}

template < typename V, typename E >
ListGraph<V, E>::~ListGraph()
{
	while (m_vertexList.length() > 0)
	{
		removeVertex();
	}
}

template < typename V, typename E >
int ListGraph<V, E>::addVertex()
{
	int ret = -1;
	Vertex* v = new Vertex();

	if (NULL != v)
	{
		if (m_vertexList.insert(v))
		{
			ret = m_vertexList.length() - 1;
		}
	}
	else
	{
		THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to addVertex in void ListGraph<V, E>::addVertex()");
	}

	return ret;
}

template < typename V, typename E >
int ListGraph<V, E>::addVertex(const V& value)
{
	int ret = -1;
	Vertex* v = new Vertex();

	if (NULL != v)
	{
		v->data = new V();
		if (NULL != v->data)
		{
			*(v->data) = value;
		}
		else
		{
			THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to create V in void ListGraph<V, E>::addVertex(const V& value)");
		}

		if (m_vertexList.insert(v))
		{
			ret = m_vertexList.length() - 1;
		}
	}
	else
	{
		THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to addVertex in void ListGraph<V, E>::addVertex(const V& value)");
	}

	return ret;
}

template < typename V, typename E >
void ListGraph<V, E>::removeVertex()
{
	if (m_vertexList.length() > 0)
	{
		int index = m_vertexList.length() - 1;
		Vertex* v = m_vertexList[index];

		for (int i = (m_vertexList.move(0), 0); !m_vertexList.end() && i != index; m_vertexList.next(), ++i)
		{
			Vertex* v = m_vertexList.current();

			for (int j = (v->edgeList.move(0), 0); !v->edgeList.end(); v->edgeList.next(), ++j)
			{
				if (v->edgeList.current().end == index)
				{
					v->edgeList.remove(j);
					break;
				}
			}
		}

		m_vertexList.remove(index);

		delete v->data;
		delete v;
	}
	else
	{
		THROW_EXCEPTION(InvalidOperationException, "Invalid operation in void ListGraph<V, E>::removeVertex()");
	}
}

template < typename V, typename E >
V& ListGraph<V, E>::getVertex(int n)
{
	if (n >= 0 && n < m_vertexList.length())
	{
		Vertex* v = m_vertexList[n];

		if (NULL != v->data)
		{
			return *(v->data);
		}
		else
		{
			THROW_EXCEPTION(InvalidOperationException, "Invalid operation in V& ListGraph<V, E>::getVertex(int n)");
		}
	}
	else
	{
		THROW_EXCEPTION(IndexOutOfBoundsException, "Index outof bounds in V& ListGraph<V, E>::getVertex(int n)");
	}
}

template < typename V, typename E >
const V& ListGraph<V, E>::getVertex(int n) const
{
	return const_cast<ListGraph<V, E>*>(this)->getVertex(n);
}

template < typename V, typename E >
bool ListGraph<V, E>::getVertex(int n, V& value) const
{
	bool ret = (n >= 0 && n < m_vertexList.length());

	Vertex* v = ret ? m_vertexList[n] : NULL;

	ret = ret && (NULL != v->data);

	if (ret)
	{
		value = *(v->data);
	}

	return ret;
}

template < typename V, typename E >
bool ListGraph<V, E>::setVertex(int n, const V& value)
{
	bool ret = (n >= 0 && n < m_vertexList.length());

	if (ret)
	{
		Vertex* vertex = m_vertexList[n];
		V* v = vertex->data;

		if (NULL == v)
		{
			v = new V();
		}

		if (NULL != v)
		{
			*v = value;

			vertex->data = v;
		}
		else
		{
			THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to create V in bool ListGraph<V, E>::setVertex(int n, const V& value)");
		}
	}

	return ret;
}

template < typename V, typename E >
SharedPointer< Array<int> > ListGraph<V, E>::getAdjacent(int n) const
{
	Array<int>* ret = NULL;

	if (n >= 0 && n < m_vertexList.length())
	{
		Vertex* v = m_vertexList[n];

		int len = v->edgeList.length();

		if (len > 0)
		{
			ret = new DynamicArray<int>(len);

			if (NULL != ret)
			{
				for (int i = (v->edgeList.move(0), 0); !v->edgeList.end(); v->edgeList.next(), ++i)
				{
					(*ret)[i] = v->edgeList.current().end;
				}
			}
			else
			{
				THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory in SharedPointer< Array<int> > ListGraph<V, E>::getAdjacent(int n) const");
			}
		}
	}

	return ret;
}

template < typename V, typename E >
E& ListGraph<V, E>::getEdge(int i, int j)
{
	if ((i >= 0 && i < m_vertexList.length()) && (j >= 0 && j < m_vertexList.length()))
	{
		Vertex* v = m_vertexList[i];

		for (v->edgeList.move(0); !v->edgeList.end(); v->edgeList.next())
		{
			if (v->edgeList.current().end == j)
			{
				return v->edgeList.current().data;
			}
		}
	}
	else
	{
		THROW_EXCEPTION(IndexOutOfBoundsException, "Index outof bounds in E& ListGraph<V, E>::getEdge(int i, int j)");
	}

	THROW_EXCEPTION(InvalidOperationException, "No such edge in E& ListGraph<V, E>::getEdge(int i, int j)");
}

template < typename V, typename E >
const E& ListGraph<V, E>::getEdge(int i, int j) const
{
	return const_cast<ListGraph<V, E>*>(this)->getEdge(i, j);
}

template < typename V, typename E >
bool ListGraph<V, E>::getEdge(int i, int j, E& value) const
{
	bool ret = (i >= 0 && i < m_vertexList.length()) && (j >= 0 && j < m_vertexList.length());

	if (ret)
	{
		Vertex* v = m_vertexList[i];
		ret = false;

		for (v->edgeList.move(0); !v->edgeList.end(); v->edgeList.next())
		{
			if (v->edgeList.current().end == j)
			{
				value = v->edgeList.current().data;
				ret = true;
				break;
			}
		}
	}
	
	return ret;
}

template < typename V, typename E >
bool ListGraph<V, E>::setEdge(int i, int j, const E& value)
{
	bool ret = (i >= 0 && i < m_vertexList.length()) && (j >= 0 && j < m_vertexList.length());
	ret = ret && (i != j);

	if (ret)
	{
		Vertex* v = m_vertexList[i];
		Edge<E>* e = NULL;

		for (v->edgeList.move(0); !v->edgeList.end(); v->edgeList.next())
		{
			if (v->edgeList.current().begin == i && v->edgeList.current().end == j)
			{
				e = &(v->edgeList.current());
				break;
			}
		}

		if (NULL == e)
		{
			ret = v->edgeList.insert(Edge<E>(value, i, j));
		}
		else
		{
			e->data = value;
		}
	}

	return ret;
}

template < typename V, typename E >
bool ListGraph<V, E>::removeEdge(int i, int j)
{
	bool ret = (i >= 0 && i < m_vertexList.length()) && (j >= 0 && j < m_vertexList.length());

	if (ret)
	{
		Vertex* v = m_vertexList[i];
		int index = -1;

		for (int k =(v->edgeList.move(0), 0); !v->edgeList.end(); v->edgeList.next(), ++k)
		{
			if ((v->edgeList.current().begin == i) && (v->edgeList.current().end == j))
			{
				index = k;
				break;
			}
		}

		if (index >= 0)
		{
			ret = v->edgeList.remove(index);
		}
	}

	return ret;
}

template < typename V, typename E >
int ListGraph<V, E>::VCount() const
{
	return m_vertexList.length();
}

template < typename V, typename E >
int ListGraph<V, E>::ECount() const
{
	int ret = 0;

	for (m_vertexList.move(0); !m_vertexList.end(); m_vertexList.next())
	{
		ret += m_vertexList.current()->edgeList.length();
	}

	return ret;
}

template < typename V, typename E >
int ListGraph<V, E>::IDegree(int n) const
{
	int ret = 0;

	if (n >= 0 && n < m_vertexList.length())
	{
		for (m_vertexList.move(0); !m_vertexList.end(); m_vertexList.next())
		{
			Vertex* v = m_vertexList.current();

			for (v->edgeList.move(0); !v->edgeList.end(); v->edgeList.next())
			{
				if (v->edgeList.current().end == n)
				{
					++ret;
				}
			}
		}
	}
	else
	{
		THROW_EXCEPTION(IndexOutOfBoundsException, "Index outof bounds in int ListGraph<V, E>::IDegree(int n) const");
	}

	return ret;
}

template < typename V, typename E >
int ListGraph<V, E>::ODegree(int n) const
{
	int ret = 0;

	if (n >= 0 && n < m_vertexList.length())
	{
		Vertex* v = m_vertexList[n];

		ret = v->edgeList.length();
	}
	else
	{
		THROW_EXCEPTION(IndexOutOfBoundsException, "Index outof bounds in int ListGraph<V, E>::ODegree(int n) const");
	}

	return ret;
}

template < typename V, typename E >
bool ListGraph<V, E>::isAdjacent(int i, int j) const
{
	bool ret = false;

	if ((i >= 0 && i < VCount()) && (j >= 0 && j < VCount()))
	{
		Vertex* v = m_vertexList[i];

		for (v->edgeList.move(0); !v->edgeList.end(); v->edgeList.next())
		{
			if (v->edgeList.current().end == j)
			{
				ret = true;
				break;
			}
		}
	}
	else
	{
		THROW_EXCEPTION(IndexOutOfBoundsException, "Index outof bounds in bool ListGraph<V, E>::isAdjacent(int i, int j) const");
	}

	return ret;
}

}

#endif